RootishArrayStack: A Space-Efficient Array Stack

The data structures that store their data in one or two arrays and avoid resizing these arrays too often, the arrays frequently are not very full. For example, immediately after a resize() operation on an ArrayStack, the backing array is only half full. Even worse, there are times when only one-third of it contains data.

Visual demonstration#

A sequence of add(i, x) and remove(i) operations on a RootishArrayStack is illustrated below. Arrows denote elements being copied.

In this lesson, we discuss the RootishArrayStack data structure, that addresses the problem of wasted space. The RootishArrayStack stores $n$ elements using $O(\sqrt n)$ arrays. In these arrays, at most $O(\sqrt n)$ array locations are unused at any time. All remaining array locations are used to store data. Therefore, these data structures waste at most $O(\sqrt n)$ space when storing $n$ elements.

A RootishArrayStack stores its elements in a list of $r$ arrays called blocks that are numbered $0,1,...,r−1$. See the above slides. Block $b$ contains $b + 1$ elements. Therefore, all $r$ blocks contain a total of

$$1 + 2 + 3 + \cdots + r = r(r + 1)/2$$

elements. The above formula can be obtained as shown in the following illustration:

In the illustration above, the number of shaded squares is the same. Together the white and shaded squares make a rectangle consisting of $r(r + 1)$ squares.

As we might expect, the elements of the list are laid out in order within the blocks. The list element with index $0$ is stored in block $0$, elements with list indices $1$ and $2$ are stored in block $1$, elements with list indices $3$, $4$, and $5$ are stored in block $2$, and so on. The main problem we have to address is that of determining, given an index $i$, which block contains $i$ as well as the index corresponding to $i$ within that block.

Determining the index of $i$ within its block turns out to be easy. If index $i$ is in block $b$, then the number of elements in blocks $0,\cdots,b−1$ is $b(b + 1)/ 2$. Therefore, $i$ is stored at location

$$j = i − b(b + 1)/2$$

within block $b$. Somewhat more challenging is the problem of determining the value of $b$. The number of elements that have indices less than or equal to $i$ is $i + 1$. On the other hand, the number of elements in blocks $0,\cdots,b$ is $(b + 1)(b + 2)/2$. Therefore, $b$ is the smallest integer such that

$$(b+1)(b+2)/2 \ge i + 1$$

We can rewrite this equation as

$$b^2 + 3b − 2i \ge 0$$

The corresponding quadratic equation $b^2 + 3b − 2i = 0$ has two solutions: $b = (−3 + \sqrt{9 + 8i})/2$ and $b = (−3 − \sqrt{9 + 8i})/2$. The second solution makes no sense in our application since it always gives a negative value. Therefore, we obtain the solution $b = (−3 + \sqrt{9 + 8i})/2$. In general, this solution is not an integer, but going back to our inequality, we want the smallest integer $b$ such that $b \ge (−3 + \sqrt{9 + 8i})/2$. This is simply

$$b = \lceil (-3 + \sqrt{9+8i})/2 \rceil$$

The RootishArrayStack operations#

With this out of the way, the get(i) and set(i, x) methods are straightforward. We first compute the appropriate block $b$ and the appropriate index $j$ within the block and then perform the appropriate operation:

If we use any of the array-based data structures for representing the blocks list, then get(i) and set(i, x) will each run in constant time.

The add(i, x) method will, by now, look familiar. We first check to see if our data structure is full, by checking if the number of blocks, $r$, is such that $r(r + 1)/2 = n$. If so, we call grow() to add another block. With this done, we shift elements with indices $i,\cdots, n−1$ to the right by one position to make room for the new element with index $i$:

The grow() method does what we expect. It adds a new block:

Ignoring the cost of the grow() operation, the cost of an add(i, x) operation is dominated by the cost of shifting and is therefore $O(1 + n − i)$, just like an ArrayStack.

The remove(i) operation is similar to add(i, x). It shifts the elements with indices $i + 1,\cdots, n$ left by one position and then, if there is more than one empty block, it calls the shrink() method to remove all but one of the unused blocks:

The implementation of the shrink() method is:

Once again, ignoring the cost of the shrink() operation, the cost of a remove(i) operation is dominated by the cost of shifting and is therefore $O(n − i).$

Explanation

Let’s start our explanation from the start of main() in main.py file.

• Line 67: It creates a new instance of the RootishArrayStack class with the type of the elements to be stored in the stack being Integer. The new instance is assigned to the variable stack.
• Lines 69–71: It adds the elements 1, 2, and 3 to the stack at indices 0, 1, and 2, respectively.
• Line 72: It prints the elements of stack.
• Line 74: It removes an element from stack from index 1 using the remove() method.
• Lines 77–78: It adds the elements 2 and 4 to stack at indices 1 and 3, respectively.
• Line 81: It clears all the elements from stack.